package leetcode.editor.cn;

//实现 strStr() 函数。 
//
// 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如
//果不存在，则返回 -1 。 
//
// 
//
// 说明： 
//
// 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 
//
// 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。 
//
// 
//
// 示例 1： 
//
// 
//输入：haystack = "hello", needle = "ll"
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：haystack = "aaaaa", needle = "bba"
//输出：-1
// 
//
// 示例 3： 
//
// 
//输入：haystack = "", needle = ""
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= haystack.length, needle.length <= 5 * 10⁴ 
// haystack 和 needle 仅由小写英文字符组成 
// 
// Related Topics 双指针 字符串 字符串匹配 👍 1181 👎 0

import java.util.Arrays;

//Java：实现 strStr()
public class ImplementStrstr_28{
    public static void main(String[] args) {
        Solution solution = new ImplementStrstr_28().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int strStr(String haystack, String needle) {
        int len1 = haystack.length(), len2 = needle.length();
        if(len2==0) return 0;
        char[] a = haystack.toCharArray(), b = needle.toCharArray();
        int[] pi = new int[len2];
        for (int i = 1,j=0; i < len2; i++) {
            while (j>0 && b[i]!=b[j])
                j=pi[j-1];
            if(b[i]==b[j]) j++; //继续累加匹配
            pi[i]=j;
        }
//        System.out.println(Arrays.toString(pi));
        for (int i = 0,j=0; i < len1; i++) {
            while(j>0 && a[i]!=b[j])
                j= pi[j-1]; //跳到匹配串的前缀位置
            if(a[i]==b[j]){
                j++;
            }
            if(j==len2) // 与匹配串匹配成功至结束
                return i-len2+1;
        }
        return -1; //没有匹配上的
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
